package leetcode.hot100;

import java.util.Arrays;
import java.util.List;

public class number76 {
    public static void main(String[] args) {
        System.out.println(minWindow("aaaaaaaaaaaabbbbbcdd","abcdd"));
    }
    public static String minWindow(String s, String t) {
        int upCount=0;
        int[] need = new int[128];
        for (char c : t.toCharArray()) { //被包含的字符串
            if(need[c-'A']==0){
                upCount++;
            }
            need[c-'A']++;
        }
        String res= "";
        int resLen=Integer.MAX_VALUE;
        int left = 0, right = 0 ,nextStart = 0;
        int[]temp=Arrays.copyOf(need,need.length);
        boolean flag=false; //是否找到第一个
        boolean flagFlag=false; //是否找到第一个的情况下标记了
        int upCountCopy=upCount;
        while(left<s.length()){
            char sc=s.charAt(right);
            if(need[sc-'A']>0){ //如果这个字符串包含
                if(flag&&!flagFlag){
                    nextStart=right;
                    flagFlag=true;
                }
                right++;
                temp[sc-'A']--;
                if(temp[sc-'A']==0){
                    upCountCopy--;
                    if(upCountCopy==0){ //如果找到了,也就是没有大于0的
                        if(right-left+1<resLen){
                            res=s.substring(left,right);
                            resLen=right-left+1;
                        }
                        left=Math.max(left+1,nextStart);
                        right=left;
                        temp=Arrays.copyOf(need,need.length);
                        upCountCopy=upCount;
                        flagFlag=false;
                    }
                }
                flag=true;
            }else{ //如果不包含
                if(right-left>0){  //如果已经开始统计
                    right++;
                }else{//如果没有开始统计 往后移动
                    left++;
                    right=left;
                }
            }
            if(right==s.length()){
                left=Math.max(left+1,nextStart);
                right=left;
                temp=Arrays.copyOf(need,need.length);
                upCountCopy=upCount;
            }
        }
        return res;
    }
}
